/**
 * https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/submissions/567434999/
 * 3186.施咒的最大总伤害
 * medium 2024.09.23
 * 多维dp
 */

class Solution {
public:
    typedef long long ll;
    long long maximumTotalDamage(vector<int>& power) {
        map<int,int> mp;
        for(auto x:power)
        mp[x]++;
        int n=mp.size();
        vector<pair<int,int>> v(mp.begin(),mp.end());
        vector<ll>dp(n+1,0);
        dp[1]=(ll)v[0].first*v[0].second;
        if(n>1){
            if(v[1].first-v[0].first<=2)
                dp[2]=max(dp[1],(ll)v[1].first*v[1].second);
            else
                dp[2]=dp[1]+(ll)v[1].first*v[1].second;
            for(int i=2;i<n;++i){
                ll sum=(ll)v[i].first*v[i].second;
                int j=i-1;
                while(j>=0&&v[i].first-v[j].first<=2){
                    j--;
                }
                dp[i+1]=max(dp[i],sum+dp[j+1]);
        }
        }
        return dp[n];
    }
};